//
// Created by ade on 2022/9/15.
//

// 1. vector<int> 并归算法
#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int val) : val(val), next(nullptr) {}
};

void showVec(vector<int> &nums) {
    for (auto i : nums) {
        cout << i << ",";
    }
    cout << endl;
}

void mergeVec(vector<int> &nums, int left, int right) {
    int i = left, mid = (left + right) / 2, j = mid + 1;
    vector<int> tmp = {};
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp.push_back(nums[i++]);
        } else {
            tmp.push_back(nums[j++]);
        }
    }
    while (i <= mid) tmp.push_back(nums[i++]);
    while (j <= right) tmp.push_back(nums[j++]);
    int k = 0;
    while (k < right - left + 1) {
        nums[left + k] = tmp[k];
        k++;
    }
}

void splitVec(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    splitVec(nums, left, mid);
    splitVec(nums, mid + 1, right);
    mergeVec(nums, left, right);
}

void showListNode(ListNode *head) {
    while (head) {
        cout << head->val << ",";
        head = head->next;
    }
    cout << endl;
}

ListNode *init() {
    vector<int> nums = {4, 7, 6, 3, 9, 8, 1, 12, 31, 2, 1, -1, 99};
    ListNode *head = new ListNode(nums[0]);
    ListNode *index = head;
    for (int i = 1; i < nums.size(); i++) {
        ListNode *tmp = new ListNode(nums[i]);
        index->next = tmp;
        index = index->next;
    }
    return head;
}

ListNode *getMid(ListNode *start, ListNode *end) {
    if (!start || !start->next) return start;
    ListNode *slow = start;
    ListNode *fast = start->next;
    while (fast->next != end) {
        fast = fast->next;
        slow = slow->next;
        if (fast->next != end) fast = fast->next;
    }
    return slow;
}

ListNode *merge(ListNode *start, ListNode *end) {

}

ListNode *split(ListNode *start, ListNode *end) {
    if(start->next == end || start == end) return start;

}


int main() {
//    vector<int> nums = {4, 7, 6, 3, 9, 8, 1, 12, 31, 2, 1, -1, 99};
//    splitVec(nums, 0, nums.size() - 1);
//    showVec(nums);
    ListNode *head = init();
    return 0;
}